#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define NORMAL 0 //表示没有
#define THRENA 1 //表示有
//这里左儿子记录前驱，右儿子记录后继

// 中序
typedef struct Node {
    int val, ltag, rtag;///val结点的值，ltag记录是否有前驱,rtag记录是否有后继
    struct Node *lchild, *rchild; 
} Node;
 
Node *getNewNode(int val) {///获取新的结点
    Node *p = (Node *)malloc(sizeof(Node));
    p->val = val;
    p->lchild = p->rchild = NULL;
    p->ltag = p->rtag = NORMAL;//NORMAL表示还未有前驱或后继
    return p;
}
 
Node *insert(Node *root, int val) {//添加结点，组成普通的二叉树
    if (!root) return getNewNode(val);
    if (root->val == val) return root;
    if (root->val > val) root->lchild = insert(root->lchild, val);
    else root->rchild = insert(root->rchild, val);
    return root;
}
 
 
 
void in_order(Node *root) {//普通递归中序遍历
    if (!root) return ;
    if (root->ltag == NORMAL) in_order(root->lchild);
    printf("%d ", root->val);
    if (root->rtag == NORMAL) in_order(root->rchild);
    return ;
}
 
void build_Thread(Node *root) {//建立线索化
    if (!root) return ;
    static Node *pre = NULL;//使用静态变量使得pre值不随函数递归过程改变而改变
    build_Thread(root->lchild);//由于是中序遍历，先递归到最左结点
    //中间过程就是想当于根节点
    if (root->ltag = NORMAL) {
        root->lchild = pre;
        root->ltag = THRENA;
    }
    if (pre && pre->rchild == NORMAL) {
        pre->rchild = root; 
        pre->rtag = THRENA;
    }
    pre = root;
    build_Thread(root->rchild);//然后再遍历右子树
    return ;
}
 
Node *most_left(Node *root) {//找到最左结点
    Node *temp = root;
    while (temp && temp->ltag == NORMAL && temp->lchild != NULL) temp = temp->lchild;
    return temp;
}
 
void output(Node *root) {
    if (!root) ;
    Node *p = most_left(root);//从最左结点开始遍历
    while (p) {
        printf("%d ", p->val);
        if (p->rtag == THRENA) p = p->rchild;//如果后继存在进行遍历后继
        else p = most_left(p->rchild);//找到右子树的最左结点继续遍历
    }
    return ;
}
 
void clear(Node *root) {
    if (!root) return ;
    if (root->ltag == NORMAL) clear(root->lchild);
    if (root->rtag == NORMAL) clear(root->rchild);
    free(root);
    return ;
}
 
int main() {
    srand(time(0));    
    Node *root = NULL;
    for (int i = 0; i < 10; i++) {
        int val = rand() % 100;
        root = insert(root, val);
    }
    in_order(root);
    putchar(10);
    build_Thread(root);
    output(root);
    putchar(10);
    clear(root);
    return 0;
}
